package com.lds.offer.demo;

import java.util.HashMap;

/**
 * @description: Offer 39. 数组中出现次数超过一半的数字
 * @author: lds
 * @create: 2022-10-09 15:56
 **/
public class Offer_39_数组中出现次数超过一半的数字 {

    //https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/

    /**
     * 设置两个变量，第一个变量x为数组中某个元素的值，第二个变量count为出现的次数
     * 遍历数组，当count=0时，将当前遍历的值赋予x
     * 当前遍历的值等于x时，count+1
     * 当前遍历的值不等于x时，count-1
     */

    public static void main(String[] args) {
        int[] arr = new int[]{2,2,1,1,1,2,2};
        int i = find(arr);
        System.out.println(i);
    }

    public static int find(int[] arr) {
        int x = arr[0], count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (count == 0) {
                x = arr[i];
            }
            if (arr[i] == x) {
                count++;
            }else {
                count--;
            }
        }
        return x;
    }
}
